import java.util.*;


public class ExamNetEase2021082104 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最小航行费用
     * @param input int整型二维数组 二维网格
     * @return int整型
     */
    public int minSailCost (int[][] input) {
        // write code here
        r = input.length;
        if(r==0){
            return -1;
        }
        c =input[0].length;
        if(c==0){
            return -1;
        }
        this.input = input;
        dfs(1,0,0);
        dfs(0,1,0);
        return min==Integer.MAX_VALUE?-1:min;
    }
    private int[][] input;
    private int r,c;
    private int min = Integer.MAX_VALUE;
    public void dfs(int x,int y,int sum) {
        if(sum>min||x>=r||y>=c){
            return;
        }
        if (input[x][y]==2){
            return;
        }
        sum=sum+2-input[x][y];
        if(x==r-1&&y==c-1){
            min = Math.min(min,sum);
            return;
        }
        dfs(x+1,y,sum);
        dfs(x,y+1,sum);
    }
}